package cn.arnold.hash;

public class HashTable {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);
        Emp emp1 = new Emp(1, "arnold");
        Emp emp2 = new Emp(2, "zlatan");
        Emp emp3 = new Emp(3, "lavine");
        Emp emp4 = new Emp(10, "pogab");
        hashTab.add(emp1);
        hashTab.add(emp2);
        hashTab.add(emp3);
        hashTab.add(emp4);
        hashTab.list();
        hashTab.findById(2);
    }
}


// 存放的数据对象：员工
class Emp {
    public int id;
    public String name;
    public Emp next;    //指向下一个对象的域，默认为null

    // 构造器
    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

// 链表
class EmpLinkedList {
    Emp head = null;    // 头结点

    /**
     * 添加到链表的末尾: id从低到高
     *
     * @param emp
     */
    public void add(Emp emp) {
        // 添加第一个
        if (head == null) {
            head = emp;
            return;
        }
        // 不是第一个，则先找到链表末尾，添加到后面
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next; // 后移
        }
        // 找到末尾后添加
        curEmp.next = emp;
    }

    /**
     * 遍历某条链表的雇员信息并显示
     *
     * @param no
     */
    public void show(int no) {
        // 链表为空则结束
        if (head == null) {
            System.out.println("第" + (no + 1) + "条链表为空...");
            return;
        }
        // 遍历链表的雇员信息并显示
        Emp curEmp = head;
        while (true) {
            System.out.println("第" + (no + 1) + "条链表的信息为=>id=" + curEmp.id + ", name=" + curEmp.name);
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next; // 指针后移
        }
    }

    /**
     * 根据id查找
     * @param id
     * @return
     */
    public Emp findById(int id) {
        if (head == null) {
            System.out.println("链表为空...");
            return null;
        }
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) { //找到退出
                break;
            }
            if (curEmp.next == null) { //遍历完也没找到退出
                curEmp = null;
                break;
            }
            curEmp = curEmp.next; //索引指针后移
        }
        return curEmp;
    }
}

// 数组：数组里存放链表
class HashTab {
    private EmpLinkedList[] empLinkedListArray;     // 管理链表的数组
    private int size;           // 管理的链表的条数

    // 构造器
    public HashTab(int size) {
        this.size = size;
        // 初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        // !!!初始化每条链表
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    /**
     * 添加操作
     *
     * @param emp
     */
    public void add(Emp emp) {
        // 根据id（索引）判断应该添加到哪条链表===> 散列函数
        int no = hashMapper(emp.id);    // 待添加位置的索引
        // 添加到对应的链表中去
        empLinkedListArray[no].add(emp);
    }

    /**
     * 遍历所有链表
     */
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].show(i);
        }
    }

    /**
     * 根据id查找员工
     * @param id
     */
    public void findById(int id){
        // 确定当前id在哪条链表
        int no = hashMapper(id);
        Emp resEmp = empLinkedListArray[no].findById(id);
        if (resEmp==null){
            System.out.println("没有找到该员工...");
        }else {
            System.out.println("在"+(no+1)+"条链表中找到员工\n"+"员工信息："+resEmp);
        }
    }
    /**
     * 散列函数
     *
     * @param id
     * @return
     */
    public int hashMapper(int id) {
        return id % size;
    }
}